home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / gnu / nethack.lha / nethack-3.1 / src / mkmap.c < prev    next >
C/C++ Source or Header  |  1993-01-22  |  10KB  |  403 lines
  1. /*    SCCS Id: @(#)mkmap.c    3.1    92/07/15    */
  2. /* Copyright (c) J. C. Collet, M. Stephenson and D. Cohrs, 1992   */
  3. /* NetHack may be freely redistributed.  See license for details. */
  4.  
  5. #include "hack.h"
  6. #include "sp_lev.h"
  7.  
  8. #define    HEIGHT    (ROWNO - 1)
  9. #define WIDTH    (COLNO - 2)
  10.  
  11. static void FDECL(init_map,(SCHAR_P));
  12. static void FDECL(init_fill,(SCHAR_P,SCHAR_P));
  13. static schar FDECL(get_map,(int,int,SCHAR_P));
  14. static void FDECL(pass_one,(SCHAR_P,SCHAR_P));
  15. static void FDECL(pass_two,(SCHAR_P,SCHAR_P));
  16. static void FDECL(pass_three,(SCHAR_P,SCHAR_P));
  17. static void NDECL(wallify_map);
  18. static void FDECL(join_map,(SCHAR_P,SCHAR_P));
  19. static void FDECL(finish_map,(SCHAR_P,SCHAR_P,XCHAR_P,XCHAR_P));
  20. void FDECL(mkmap, (lev_init *));
  21.  
  22. char *new_locations;
  23. int min_rx, max_rx, min_ry, max_ry; /* rectangle bounds for regions */
  24. static int n_loc_filled;
  25.  
  26. static void
  27. init_map(bg_typ)
  28.     schar    bg_typ;
  29. {
  30.     register int i,j;
  31.  
  32.     for(i=1; i<COLNO; i++)
  33.         for(j=0; j<ROWNO; j++)
  34.         levl[i][j].typ = bg_typ;
  35. }
  36.  
  37. static void
  38. init_fill(bg_typ, fg_typ)
  39.     schar    bg_typ, fg_typ;
  40. {
  41.     register int i,j;
  42.     long limit, count;
  43.  
  44.     limit = (WIDTH * HEIGHT * 2) / 5;
  45.     count = 0;
  46.     while(count < limit) {
  47.         i = rn1(WIDTH-1, 2);
  48.         j = rnd(HEIGHT-1);
  49.         if (levl[i][j].typ == bg_typ) {
  50.         levl[i][j].typ = fg_typ;
  51.         count++;
  52.         }
  53.     }
  54. }
  55.  
  56. static schar
  57. get_map(col,row, bg_typ)
  58.     int col,row;
  59.     schar    bg_typ;
  60. {
  61.     if (col <= 0 || row < 0 || col > WIDTH || row >= HEIGHT)
  62.         return bg_typ;
  63.     return levl[col][row].typ;
  64. }
  65.  
  66. static int dirs[16] = {
  67.     -1, -1 /**/, -1, 0 /**/, -1, 1 /**/,
  68.      0, -1 /**/,              0, 1 /**/,
  69.      1, -1 /**/,  1, 0 /**/,  1, 1};
  70.  
  71. static void
  72. pass_one(bg_typ, fg_typ)
  73.     schar    bg_typ, fg_typ;
  74. {
  75.     register int i,j;
  76.     short count, dr;
  77.  
  78.     for(i=2; i<=WIDTH; i++)
  79.         for(j=1; j<HEIGHT; j++) {
  80.         for(count=0, dr=0; dr < 8; dr++)
  81.             if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
  82.                                 == fg_typ)
  83.             count++;
  84.  
  85.         switch(count) {
  86.           case 0 : /* death */
  87.           case 1 :
  88.           case 2:
  89.               levl[i][j].typ = bg_typ;
  90.               break;
  91.           case 5:
  92.           case 6:
  93.           case 7:
  94.           case 8:
  95.               levl[i][j].typ = fg_typ;
  96.               break;
  97.           default:
  98.               break;
  99.           }
  100.         }
  101. }
  102.  
  103. #define new_loc(i,j)    *(new_locations+ ((j)*(WIDTH+1)) + (i))
  104.  
  105. static void
  106. pass_two(bg_typ, fg_typ)
  107.     schar    bg_typ, fg_typ;
  108. {
  109.     register int i,j;
  110.     short count, dr;
  111.  
  112.     for(i=2; i<=WIDTH; i++)
  113.         for(j=1; j<HEIGHT; j++) {
  114.         for(count=0, dr=0; dr < 8; dr++)
  115.             if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
  116.                                 == fg_typ)
  117.             count++;
  118.             if (count == 5)
  119.             new_loc(i,j) = bg_typ;
  120.             else
  121.             new_loc(i,j) = get_map(i,j, bg_typ);
  122.         }
  123.  
  124.     for(i=2; i<=WIDTH; i++)
  125.         for(j=1; j<HEIGHT; j++)
  126.         levl[i][j].typ = new_loc(i,j);
  127. }
  128.  
  129. static void
  130. pass_three(bg_typ, fg_typ)
  131.     schar    bg_typ, fg_typ;
  132. {
  133.     register int i,j;
  134.     short count, dr;
  135.  
  136.     for(i=2; i<=WIDTH; i++)
  137.         for(j=1; j<HEIGHT; j++) {
  138.         for(count=0, dr=0; dr < 8; dr++)
  139.             if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
  140.                                 == fg_typ)
  141.             count++;
  142.         if (count < 3)
  143.             new_loc(i,j) = bg_typ;
  144.         else
  145.             new_loc(i,j) = get_map(i,j, bg_typ);
  146.         }
  147.  
  148.     for(i=2; i<=WIDTH; i++)
  149.         for(j=1; j<HEIGHT; j++)
  150.         levl[i][j].typ = new_loc(i,j);
  151. }
  152.  
  153. /*
  154.  * use a flooding algorithm to find all locations that should
  155.  * have the same rm number as the current location.
  156.  * if anyroom is TRUE, use IS_ROOM to check room membership instead of
  157.  * exactly matching levl[sx][sy].typ and walls are included as well.
  158.  */
  159. void
  160. flood_fill_rm(sx, sy, rmno, lit, anyroom)
  161.     int sx;
  162.     register int sy;
  163.     register int rmno;
  164.     boolean lit;
  165.     boolean anyroom;
  166. {
  167.     register int i;
  168.     int nx;
  169.     schar fg_typ = levl[sx][sy].typ;
  170.  
  171.     /* back up to find leftmost uninitialized location */
  172.     while(sx > 0
  173.       && (anyroom ? IS_ROOM(levl[sx][sy].typ) : levl[sx][sy].typ == fg_typ)
  174.       && levl[sx][sy].roomno != rmno)
  175.     sx--;
  176.     sx++; /* compensate for extra decrement */
  177.  
  178.     /* assume sx,sy is valid */
  179.     if(sx < min_rx) min_rx = sx;
  180.     if(sy < min_ry) min_ry = sy;
  181.  
  182.     for(i=sx; i<=WIDTH && levl[i][sy].typ == fg_typ; i++) {
  183.     levl[i][sy].roomno = rmno;
  184.     levl[i][sy].lit = lit;
  185.     if(anyroom) {
  186.         /* add walls to room as well */
  187.         register int ii,jj;
  188.         for(ii= (i == sx ? i-1 : i); ii <= i+1; ii++)
  189.         for(jj = sy-1; jj <= sy+1; jj++)
  190.             if(isok(ii,jj) &&
  191.                (IS_WALL(levl[ii][jj].typ) ||
  192.             IS_DOOR(levl[ii][jj].typ))) {
  193.             levl[ii][jj].edge = 1;
  194.             if(lit) levl[ii][jj].lit = lit;
  195.             if (levl[ii][jj].roomno != rmno)
  196.                 levl[ii][jj].roomno = SHARED;
  197.             else
  198.                 levl[ii][jj].roomno = rmno;
  199.             }
  200.     }
  201.     n_loc_filled++;
  202.     }
  203.     nx = i;
  204.  
  205.     if(isok(sx,sy-1))
  206.     for(i=sx; i<nx; i++)
  207.         if(levl[i][sy-1].typ == fg_typ) {
  208.         if(levl[i][sy-1].roomno != rmno)
  209.             flood_fill_rm(i,sy-1,rmno,lit,anyroom);
  210.         } else {
  211.         if((i>sx || isok(i-1,sy-1)) &&
  212.               levl[i-1][sy-1].typ == fg_typ) {
  213.             if(levl[i-1][sy-1].roomno != rmno)
  214.             flood_fill_rm(i-1,sy-1,rmno,lit,anyroom);
  215.         }
  216.         if((i<nx-1 || isok(i+1,sy-1)) &&
  217.               levl[i+1][sy-1].typ == fg_typ) {
  218.             if(levl[i+1][sy-1].roomno != rmno)
  219.             flood_fill_rm(i+1,sy-1,rmno,lit,anyroom);
  220.         }
  221.         }
  222.     if(isok(sx,sy+1))
  223.     for(i=sx; i<nx; i++)
  224.         if(levl[i][sy+1].typ == fg_typ) {
  225.         if(levl[i][sy+1].roomno != rmno)
  226.             flood_fill_rm(i,sy+1,rmno,lit,anyroom);
  227.         } else {
  228.         if((i>sx || isok(i-1,sy+1)) &&
  229.               levl[i-1][sy+1].typ == fg_typ) {
  230.             if(levl[i-1][sy+1].roomno != rmno)
  231.             flood_fill_rm(i-1,sy+1,rmno,lit,anyroom);
  232.         }
  233.         if((i<nx-1 || isok(i+1,sy+1)) &&
  234.               levl[i+1][sy+1].typ == fg_typ) {
  235.             if(levl[i+1][sy+1].roomno != rmno)
  236.             flood_fill_rm(i+1,sy+1,rmno,lit,anyroom);
  237.         }
  238.         }
  239.  
  240.     if(nx > max_rx) max_rx = nx - 1; /* nx is just past valid region */
  241.     if(sy > max_ry) max_ry = sy;
  242. }
  243.  
  244. /*
  245.  *    If we have drawn a map without walls, this allows us to
  246.  *    auto-magically wallify it.  Taken from lev_main.c.
  247.  */
  248. static void
  249. wallify_map()
  250. {
  251.  
  252.     int x, y, xx, yy;
  253.  
  254.     for(x = 1; x < COLNO; x++)
  255.     for(y = 0; y < ROWNO; y++)
  256.         if(levl[x][y].typ == STONE) {
  257.         for(yy = y - 1; yy <= y+1; yy++)
  258.             for(xx = x - 1; xx <= x+1; xx++)
  259.             if(isok(xx,yy) && levl[xx][yy].typ == ROOM) {
  260.                 if(yy != y)    levl[x][y].typ = HWALL;
  261.                 else    levl[x][y].typ = VWALL;
  262.             }
  263.         }
  264. }
  265.  
  266. static void
  267. join_map(bg_typ, fg_typ)
  268.     schar    bg_typ, fg_typ;
  269. {
  270.     register struct mkroom *croom, *croom2;
  271.  
  272.     register int i, j;
  273.     int sx, sy;
  274.     coord sm, em;
  275.  
  276.     /* first, use flood filling to find all of the regions that need joining */
  277.     for(i=2; i<=WIDTH; i++)
  278.     for(j=1; j<HEIGHT; j++) {
  279.         if(levl[i][j].typ == fg_typ && levl[i][j].roomno == NO_ROOM) {
  280.         min_rx = max_rx = i;
  281.         min_ry = max_ry = j;
  282.         n_loc_filled = 0;
  283.         flood_fill_rm(i,j,nroom+ROOMOFFSET,FALSE,FALSE);
  284.         if(n_loc_filled > 3) {
  285.             add_room(min_rx, min_ry, max_rx, max_ry,
  286.                  FALSE, OROOM, TRUE);
  287.             rooms[nroom-1].irregular = TRUE;
  288.             if(nroom >= (MAXNROFROOMS*2))
  289.             goto joinm;
  290.         } else {
  291.             /*
  292.              * it's a tiny hole; erase it from the map to avoid
  293.              * having the player end up here with no way out.
  294.              */
  295.             for(sx = min_rx; sx<=max_rx; sx++)
  296.             for(sy = min_ry; sy<=max_ry; sy++)
  297.                 if(levl[sx][sy].roomno == nroom+ROOMOFFSET) {
  298.                 levl[sx][sy].typ = bg_typ;
  299.                 levl[sx][sy].roomno = NO_ROOM;
  300.                 }
  301.         }
  302.         }
  303.     }
  304.  
  305. joinm:
  306.     /*
  307.      * Ok, now we can actually join the regions with fg_typ's.
  308.      * The rooms are already sorted due to the previous loop,
  309.      * so don't call sort_rooms(), which can screw up the roomno's
  310.      * validity in the levl structure.
  311.      */
  312.     for(croom = &rooms[0], croom2 = croom + 1; croom2 < &rooms[nroom]; ) {
  313.     /* pick random starting and end locations for "corridor" */
  314.     if(!somexy(croom, &sm) || !somexy(croom2, &em)) {
  315.         /* ack! -- the level is going to be busted */
  316.         /* arbitrarily pick centers of both rooms and hope for the best */
  317.         impossible("No start/end room loc in join_map.");
  318.         sm.x = croom->lx + ((croom->hx - croom->lx) / 2);
  319.         sm.y = croom->ly + ((croom->hy - croom->ly) / 2);
  320.         em.x = croom2->lx + ((croom2->hx - croom2->lx) / 2);
  321.         em.y = croom2->ly + ((croom2->hy - croom2->ly) / 2);
  322.     }
  323.  
  324.     (void) dig_corridor(sm, em, FALSE, fg_typ, bg_typ);
  325.  
  326.     /* choose next region to join */
  327.     /* only increment croom if croom and croom2 are non-overlapping */
  328.     if(croom2->lx > croom->hx ||
  329.        ((croom2->ly > croom->hy || croom2->hy < croom->ly) && rn2(3))) {
  330.         croom = croom2;
  331.     }
  332.     croom2++; /* always increment the next room */
  333.     }
  334. }
  335.  
  336. static void
  337. finish_map(fg_typ, bg_typ, lit, walled)
  338.         schar    fg_typ, bg_typ;
  339.         boolean    lit, walled;
  340. {
  341.     int    i, j;
  342.  
  343.     if(walled) wallify_map();
  344.  
  345.     if(lit) {
  346.         for(i=1; i<COLNO; i++)
  347.         for(j=0; j<ROWNO; j++)
  348.             if((!IS_ROCK(fg_typ) && levl[i][j].typ == fg_typ) ||
  349.                (!IS_ROCK(bg_typ) && levl[i][j].typ == bg_typ) ||
  350.             (walled && IS_WALL(levl[i][j].typ)))
  351.             levl[i][j].lit = TRUE;
  352.         for(i = 0; i < nroom; i++)
  353.         rooms[i].rlit = 1;
  354.     }
  355. }
  356.  
  357. #define    N_P1_ITER    1    /* tune map generation via this value */
  358. #define    N_P2_ITER    1    /* tune map generation via this value */
  359. #define    N_P3_ITER    2    /* tune map smoothing via this value */
  360.  
  361. void
  362. mkmap(init_lev)
  363.  
  364.     lev_init    *init_lev;
  365. {
  366.     schar    bg_typ = init_lev->bg,
  367.         fg_typ = init_lev->fg;
  368.     boolean smooth = init_lev->smoothed,
  369.                 join = init_lev->joined;
  370.         xchar   lit = init_lev->lit,
  371.                 walled = init_lev->walled;
  372.     int i;
  373.  
  374.     if(lit < 0)
  375.         lit = (rnd(1+abs(depth(&u.uz))) < 11 && rn2(77)) ? 1 : 0;
  376.  
  377.     new_locations = (char *)alloc((WIDTH+1) * HEIGHT);
  378.  
  379.     init_map(bg_typ);
  380.     init_fill(bg_typ, fg_typ);
  381.  
  382.     for(i = 0; i < N_P1_ITER; i++)
  383.         pass_one(bg_typ, fg_typ);
  384.  
  385.     for(i = 0; i < N_P2_ITER; i++)
  386.     pass_two(bg_typ, fg_typ);
  387.  
  388.     if(smooth)
  389.         for(i = 0; i < N_P3_ITER; i++)
  390.         pass_three(bg_typ, fg_typ);
  391.  
  392.     if(join)
  393.         join_map(bg_typ, fg_typ);
  394.  
  395.     finish_map(fg_typ, bg_typ, (boolean)lit, (boolean)walled);
  396.     /* a walled, joined level is cavernous, not mazelike -dlc */
  397.     if (walled && join) {
  398.         level.flags.is_maze_lev = FALSE;
  399.         level.flags.is_cavernous_lev = TRUE;
  400.     }
  401.     free(new_locations);
  402. }
  403.